#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    void AdjustUp(vector<int>& heap, int e) {
        if (heap.empty()) {
            heap.emplace_back(e);
            return;
        }
        // 创建堆
        heap.emplace_back(e);
        int child = heap.size() - 1;

        int parent = (child - 1) / 2;
        while (child > 0) {
            // 创建大堆
            if (heap[child] > heap[parent]) {
                swap(heap[child], heap[parent]);
                child = parent;
                parent = (child - 1) / 2;
            } else {
                return;
            }
        }
    }

    void buildheap(vector<int>& nums) {
        vector<int> heap;
        for (auto e : nums)
            AdjustUp(heap, e);
        nums = heap;
    }

    void AdjustDown(vector<int>& nums) {
        // 交换最后一个位置之后，将最后一个位置弹出
        swap(nums.front(), nums.back());
        nums.pop_back();
        int size = nums.size();
        int parent = 0;
        int child = parent * 2 + 1;
        if (child + 1 < size && nums[child + 1] > nums[child])
            child++;
        while (child < size) {
            if (nums[child] > nums[parent]) {
                swap(nums[child], nums[parent]);
                parent = child;
                child = parent * 2 + 1;
                if (child + 1 < size && nums[child + 1] > nums[child])
                    child++;
            } else {
                return;
            }
        }
    }

    void PopElement(vector<int>& nums, int num) {
        // 使用向下调整算法
        while (num--) {
            AdjustDown(nums);
        }
    }

    int findKthLargest(vector<int>& nums, int k) {
        // priority_queue<int> pq;
        // for (auto e : nums) pq.push(e);
        // int ret = 0;
        // while (k--) {
        //     ret = pq.top();
        //     pq.pop();
        // }
        // return ret;
        // 自己写一个堆
        // 建堆
        // buildheap(nums);
        // // 弹出 k - 1 个元素
        // PopElement(nums, k - 1);
        // return nums[0];

        // 快速选择算法
        srand(time(NULL));
        return QS(nums, 0, nums.size() - 1, k);
    }

    int QS(vector<int>& arr, int l, int r, int k) {
        if (l >= r) return arr[l];
        int key = getkey(arr, l, r);
        int left  = l - 1, right = r + 1;
        int i = l;
        while (i < right) {
            if (arr[i] < key) swap(arr[++left], arr[i++]);
            else if (arr[i] == key) i++;
            else swap(arr[--right], arr[i]);
        }
        // 找到各个区间的数量
        int c = r - right + 1, a = left - l + 1;
        int b = r - l - c - a + 1;
        if (c >= k) return QS(arr, right, r, k);
        else if (b + c >= k) return key;
        k = k - b - c;
        return QS(arr, l, left, k);
    }

    int getkey(vector<int>& arr, int l, int r) {
        int index = l + rand() % (r - l + 1);
        return arr[index];
    }
};

class Solution {
public:
    vector<int> smallestK(vector<int>& arr, int k) {
        // 使用快速选择算法
        // 获取到对应的下标
        if (k == 0) return vector<int>();
        int index = QSselect(arr, 0, arr.size() - 1, k);
        return vector<int>(arr.begin(), arr.begin() + k);
    }

    int QSselect(vector<int>& arr, int l, int r, int k) {
        if (l == r) return l;
        int index = getIndex(arr, l, r);
        int key = arr[index];

        int left = l - 1, right = r + 1, i = l;
        while (i < right) {
            if (arr[i] < key) swap(arr[++left], arr[i++]);
            else if (arr[i] == key) i++;
            else swap(arr[--right], arr[i]);
        }
        int a = left - l + 1, c = r - right;
        int b = right - left - 1;
        // a >= k，直接到 左区间找
        if (a > k) return QSselect(arr, l, left, k);
        else if (a + b >= k) return index;

        k = k - a - b;
        return QSselect(arr, right, r, k);
    }

    int getIndex(vector<int>& arr, int l, int r) {
        return l + rand() % (r - l + 1);
    }
};

class Solution {
public:

    vector<int> sortArray(vector<int>& nums) {
        // QS(nums, 0, nums.size() - 1);
        // return nums;
        MergeSort(nums, 0, nums.size() - 1);

        return nums;
    }

    void MergeSort(vector<int>& nums, int left, int right) {
        if (left == right)
            return;
        int mid = left + (right - left) / 2;
        MergeSort(nums, left, mid);
        MergeSort(nums, mid + 1, right);
        // 左右两个区间已经排序好，现在将其组合起来
        int begin1 = left, end1 = mid;
        int begin2 = mid + 1, end2 = right;

        vector<int> copy;
        while (begin1 <= end1 && begin2 <= end2) {
            if (nums[begin1] < nums[begin2]) {
                copy.emplace_back(nums[begin1]);
                begin1++;
            } else {
                copy.emplace_back(nums[begin2]);
                begin2++;
            }
        }

        while (begin1 <= end1) {
            copy.emplace_back(nums[begin1]);
            begin1++;
        }

        while (begin2 <= end2) {
            copy.emplace_back(nums[begin2]);
            begin2++;
        }

        // nums 的 [left, right] 区间替换为 copy
        int cnt = 0;
        for (int i = left; i <= right; i++) {
            nums[i] = copy[cnt++];
        }
    }

};

class Solution {
    vector<int> temp;
public:
    int reversePairs(vector<int>& record) {
        temp.resize(record.size());
        return MergeCount(record, 0, record.size() - 1);
    }

    int MergeCount(vector<int>& arr, int left, int right) {
        if (left >= right) return 0;
        int mid = left + (right - left) / 2;
        int leftcount = MergeCount(arr, left, mid);
        int rightcount = MergeCount(arr, mid + 1, right);
        // 现在左右两边已经计算结束，并且有序
        int curleft = left, curright = mid + 1, i = 0;
        int midcount = 0;
        // 先计算
        while (curleft <= mid && curright <= right) {
            if (arr[curleft] <= arr[curright]) curleft++;
            else midcount += mid - curleft + 1, curright++;
        }

        // 后排序
        curleft = left, curright = mid + 1, i = 0;
        while (curleft <= mid && curright <= right) {
            temp[i++] = arr[curleft] > arr[curright] ? arr[curright++] : arr[curleft++];
        }
        while (curleft <= mid) temp[i++] = arr[curleft++];
        while (curright <= right) temp[i++] = arr[curright++];

        for (int i = left; i <= right; i++) arr[i] = temp[i - left];

        return midcount + leftcount + rightcount;
    }
};

class Solution {
public:
    vector<int> index, ret, tmp, indextmp;
    vector<int> countSmaller(vector<int>& nums) {
        int len = nums.size();
        index.resize(len), ret.resize(len), tmp.resize(len),
            indextmp.resize(len);
        for (int i = 0; i < len; i++)
            index[i] = i;
        MergeCal(nums, 0, len - 1);
        return ret;
    }

    void MergeCal(vector<int>& nums, int left, int right) {
        if (left >= right)
            return;
        int mid = left + (right - left) / 2;
        MergeCal(nums, left, mid);
        MergeCal(nums, mid + 1, right);

        int cur1 = left, cur2 = mid + 1, i = 0;
        // 先计算
        while (cur1 <= mid && cur2 <= right) {
            if (nums[cur1] <= nums[cur2])
                cur2++;
            else
                ret[index[cur1++]] += right - cur2 + 1;
        }

        // 降序排序
        cur1 = left, cur2 = mid + 1;
        while (cur1 <= mid && cur2 <= right) {
            if (nums[cur2] > nums[cur1]) {
                tmp[i] = nums[cur2];
                // 将下标变换
                indextmp[i] = index[cur2++];
            } else {
                tmp[i] = nums[cur1];
                indextmp[i] = index[cur1++];
            }
            i++;
        }

        while (cur1 <= mid) {
            tmp[i] = nums[cur1];
            // 将下标变换
            indextmp[i] = index[cur1++];
            i++;
        }

        while (cur2 <= right) {
            tmp[i] = nums[cur2];
            // 将下标变换
            indextmp[i] = index[cur2++];
            i++;
        }

        for (int i = left; i <= right; i++) {
            nums[i] = tmp[i - left];
            index[i] = indextmp[i - left];
        }
    }
};

int main() {


    return 0;
}